11103. Правильно построенные формулы

 

В правильно построенной формуле (ППФ) используются символы K, A, N, C, E, p, q, r, s, t. ППФ называется строка символов, удовлетворяющая условиям:

1. p, q, r, s, t являются ППФ;

2. Если w ППФ, то Nw также является ППФ;

3. Если w и x ППФ, то ППФ будут формулы Kwx, Awx, Cwx, Ewx.

Известно, что:

1. p, q, r, s, t являются логическими переменными, принимающими значения 0 (ложь) и 1 (истина);

2. K, A, N, C, E являются обозначениями логических операций: and, or, not, implies и equals соответственно. Таблицы истинностей функций представлены в таблице:

w

x

Kwx

Awx

Nw

Cwx

Ewx

1

1

1

1

0

1

1

1

0

0

1

0

0

0

0

1

0

1

1

1

0

0

0

0

0

1

1

1

Из входной строки необходимо выбрать такое подмножество символов, из которых можно построить самую длинную ППФ.

 

Вход. Каждая строка содержит от 1 до 100 символов. Последняя строка содержит 0 и не обрабатывается.

 

Выход. Для каждой входной строки вывести самую длинную ППФ, которую можно построить из подмножества ее символов. Если из символов строки никакую ППФ построить нельзя, то вывести строку “no WFF possible”.

 

Пример входа

qKpNq

KKN

0

 

Пример выхода

KqNq

no WFF possible

 

 

РЕШЕНИЕ

синтаксический анализ

 

Анализ алгоритма

Занесем все терминальные символы в массив var, нетерминальные – в op. При этом символы, которые не принадлежат множеству {K, A, N, C, E, p, q, r, s, t}, просто игнорируем.

Максимальную по длине формулу строим следующим образом: сначала ставим все операции отрицания ‘N’, за которой идут бинарные операции. Пусть во входной строке имеется n операций отрицания, m бинарных операций f1, f2, …, fm и x терминальных символов t1, t2, …, tx. Тогда длина искомой ППФ равна n + 2 * min(m, x – 1) + 1, а ее структура имеет вид:

NN…Nf1t1f2t2…fptptp+1,

где p = min(m, x – 1).

 

Реализация алгоритма

В массиве s храним входную строку. Вектор var содержит терминальные символы {p, q, r, s, t} входной строки,  op – нетерминальные {K, A, N, C, E}. В строке res строим результирующую самую длинную ППФ.

 

char s[101];

string res;

vector<char> op, var;

 

Функция is_term(c) возвращает 1, если символ с является терминальным и 0 иначе. Функция is_neterm(c) проверяет, является ли символ c нетерминальным.

 

int is_term(char c)

{

  return ((c == 'p') || (c == 'q') || (c == 'r') ||

          (c == 's') || (c == 't'));

}

 

int is_neterm(char c)

{

  return ((c == 'K') || (c == 'A') || (c == 'C') || (c == 'E'));

}

 

Основной цикл программы. Читаем входную строку в массив символов s. Очищаем массивы var и op.

 

  while(gets(s))

  {

    if (s[0] == '0') break;

    var.clear(); op.clear();

 

Просматриваем строку s слева направо, каждый терминальный символ заносим в массив var, нетерминальный – в op. Подсчитываем количество символов ‘N’ в переменной n.

 

    for(n = i = 0; i < strlen(s); i++)

    {

      if (is_neterm(s[i])) op.push_back(s[i]);

      if (is_term(s[i])) var.push_back(s[i]);

      if (s[i] == 'N') n++;

    }

 

Если входная строка не содержит ни одного терминального символа, то построить ППФ невозможно.

 

    if (var.empty())

    {

      printf("no WFF possible\n");

      continue;

    }

 

Создание результирующей строки res. Кладем n букв ‘N’ в начало строки res.

 

    i = j = 0; res = "";

    if (op.size() > 0)

    {

      for(ptr = 0; ptr < n; ptr++) res += 'N';

      while((i < op.size()) && (j < var.size() - 1))

        res = res + op[i++] + var[j++];

    }

 

Заносим в конец строки res последний терминальный символ и выводим ее.

 

    res += var[j];

    printf("%s\n",res.c_str());

  }